Skip to main content

Counting Bits

LeetCode 338 | Difficulty: Easy​

Easy

Problem Description​

Given an integer n, return an array ans of length n + 1 such that for each i* *(`0 0 1 --> 1 2 --> 10


**Example 2:**

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101


 

**Constraints:**

    - `0 <= n <= 10^5`

 

**Follow up:**

    - It is very easy to come up with a solution with a runtime of `O(n log n)`. Can you do it in linear time `O(n)` and possibly in a single pass?

    - Can you do it without using any built-in function (i.e., like `__builtin_popcount` in C++)?

**Topics:** `Dynamic Programming`, `Bit Manipulation`

---

## Approach

### Dynamic Programming

Break the problem into overlapping subproblems. Define a **state** (what information do you need?), a **recurrence** (how does state[i] depend on smaller states?), and a **base case**. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

:::tip When to use
Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).
:::

### Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

:::tip When to use
Finding unique elements, power of 2 checks, subset generation, toggling flags.
:::

---

## Solutions

### Solution 1: C# (Best: 125 ms)

| Metric | Value |
|--------|-------|
| **Runtime** | 125 ms |
| **Memory** | 38.3 MB |
| **Date** | 2022-03-01 |

```csharp title="Solution"
public class Solution {
    public int[] CountBits(int n) {
        int[] f = new int[n + 1];
    for (int i=1; i<=n; i++) f[i] = f[i >> 1] + (i & 1);
    return f;
    }
}

Complexity Analysis​

ApproachTimeSpace
Dynamic Programming$O(n)$$O(n)$
Bit Manipulation$O(n) or O(1)$$O(1)$

Interview Tips​

Key Points
  • Start by clarifying edge cases: empty input, single element, all duplicates.
  • Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
  • Consider if you can reduce space by only keeping the last row/few values.
  • LeetCode provides 3 hint(s) for this problem — try solving without them first.
💡 Hints

Hint 1: You should make use of what you have produced already.

Hint 2: Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.

Hint 3: Or does the odd/even status of the number help you in calculating the number of 1s?